| 翻訳と辞書 |
| Criss-cross algorithm ： ウィキペディア英語版 |
Criss-cross algorithm
In mathematical optimization, the criss-cross algorithm denotes a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.
Like the simplex algorithm of George B. Dantzig, the criss-cross algorithm is not a polynomial-time algorithm for linear programming. Both algorithms visit all 2''D'' corners of a (perturbed) cube in dimension ''D'', the Klee–Minty cube (after Victor Klee and George J. Minty), in the worst case.〔 However, when it is started at a random corner, the criss-cross algorithm on average visits only ''D'' additional corners.〔〔〔The simplex algorithm takes on average ''D'' steps for a cube. : 〕 Thus, for the three-dimensional cube, the algorithm visits all 8 corners in the worst case and exactly 3 additional corners on average.
==History==
The criss-cross algorithm was published independently by Tamás Terlaky〔 and 〕 and by Zhe-Min Wang; related algorithms appeared in unpublished reports by other authors.〔
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Criss-cross algorithm」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|